package test;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-08-31 18:54
 */
public class changeII {
    @Test
    public void test() {
        change(5, new int[]{1, 2, 5});

    }
    // 定义：dp[j] 表示凑满价值为j的物品的方式
    // 递推式：dp[j] += dp[j-coins[i]]
    // 初始化: dp[0] = 1(初始化为0还是1，要看测试用例)
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) { // 枚举硬币个数
            for (int j = coins[i]; j <= amount; j++) { // 枚举容量
                // 这里j 从 coins[i]开始，是为了避免j-coins[i] < 0
                dp[j] += dp[j - coins[i]];
            }
        }

        System.out.println(Arrays.toString(dp));

        return dp[amount];
    }
}
